package sort.leetcode_912;

public class QuickSort {
    public int[] sortArray(int[] nums) {
        if(nums.length == 1){
            return nums;
        }
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void quickSort(int[] nums, int lo, int hi){
        if(lo >= hi){
            return;
        }
        int r = lo + (int)(Math.random() * (hi - lo + 1));
        swap(nums, lo, r);
        int pivotIndex = partition(nums, lo, hi);
        quickSort(nums, lo, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, hi);
    }
    public int partition(int[] nums, int lo, int hi){
        //选基准元素
        int pivot = nums[lo];
        int mark = lo;
        //[lo + 1.. mark] < pivot;
        //[mark + 1... i) >= pivot;
        for(int i = lo + 1; i <= hi; i++){
            if(nums[i] < pivot){
                mark++;
                swap(nums, mark, i);
            }
        }
        nums[lo] = nums[mark];
        nums[mark] = pivot;
        return mark;
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
